import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;


public class Heavy_Coeff {

	public static Polynomial poly;
	public static int xml;
	public static Scanner sc=new Scanner(System.in);

	public static void main(String[] args){
		System.out.println("Hello dear user! Press 1 if function values are taken from xml and 0 if you want to enter them manually.");
		xml=sc.nextInt();
		System.out.println("Please enter the size of the group (N): ");
		int N=sc.nextInt();
		System.out.println("Please enter the threshold (tau): ");
		double threshold=sc.nextDouble();
		System.out.println("Please enter the probability (delta): ");
		double prob=sc.nextDouble();
		System.out.println("Please enter the inf-norm of the function: ");
		double fnorm=sc.nextDouble();
		int numof_Samples=10;
		double sqf2norm = 0;
		double probConst=1;

		if(xml==1){
			System.out.println("Please specify the path of your xml file:");
			String filename=sc.next();
			poly=xmlReader.xmlToPolynom(filename);
		}
		
		Random rnd=new Random();
		for(int majnun=0;majnun<numof_Samples;majnun++){
			sqf2norm+=Math.pow(f(rnd.nextInt(N),N).mod(),2);
		}
		sqf2norm/=numof_Samples;
		List<Set<Integer>> listof_Sets=generate_Queries(N,threshold/36,fnorm,probConst*prob/(log2(N)*Math.pow((sqf2norm/threshold),1.5)));
		Map<Integer,Complex> qfq=new HashMap<Integer,Complex>();
		for (Integer Ainteger : listof_Sets.get(0)) {
			for (Set<Integer> set : listof_Sets) {
				if(listof_Sets.get(0)==set) continue;
				for (Integer Setinteger : set) {
					if(!qfq.containsKey((Ainteger-Setinteger+N) % N)){
						qfq.put((Ainteger-Setinteger+N) % N,f((Ainteger-Setinteger+N) % N,N));
					}
				}
			}
		}
		List<Integer> L=fixed_Queries(N,threshold,listof_Sets,qfq);
		System.out.print("The heavy coefficients of the function are: ");
		for (Integer integer : L) {
			System.out.print(integer+",");
		}
	}

	private static List<Integer> fixed_Queries(int N, double threshold,
			List<Set<Integer>> listofSets, Map<Integer, Complex> qfq) {

		List<List<List<Integer>>> candidates = new ArrayList<List<List<Integer>>>();
		List<List<Integer>> firstCand=new ArrayList<List<Integer>>();
		List<Integer> simpleList=new ArrayList<Integer>();
		simpleList.add(0);
		simpleList.add(N-1);
		firstCand.add(simpleList);
		candidates.add(firstCand);
		for(int l=0;l<log2(N);l++){
			candidates.add(new ArrayList<List<Integer>>());
		}
		for(int l=0;l<log2(N);l++){
			for (List<Integer> interval : candidates.get(l)) {
				List<Integer> newinterval1=new ArrayList<Integer>(),newinterval2=new ArrayList<Integer>();
				newinterval1.add(interval.get(0));
				newinterval1.add((int) Math.floor(((interval.get(0)+interval.get(1))/2)));
				newinterval2.add((int) Math.floor(((interval.get(0)+interval.get(1))/2)) + 1);
				newinterval2.add(interval.get(1));
				int decision=distinguish(newinterval1,threshold,listofSets.get(0),listofSets.get(l+1),qfq,N);
				if(decision==1){
					candidates.get(l+1).add(newinterval1);
				}
				decision=distinguish(newinterval2,threshold,listofSets.get(0),listofSets.get(l+1),qfq,N);
				if(decision==1){
					candidates.get(l+1).add(newinterval2);
				}
			}
		}
		List<Integer> L=new ArrayList<Integer>();
		for (List<Integer> interval : candidates.get(log2(N))) {
			if(interval.get(0)==interval.get(1)) L.add(interval.get(0));
		}
		return L;
	}

	private static int distinguish(List<Integer> interval,
			double threshold, Set<Integer> A, Set<Integer> B,
			Map<Integer, Complex> qfq,int N) {
		double est=0,sqnorm=0;
		Complex sumvar=new Complex(0,0);
		Complex tempvar;
		for (Integer x : A) {
			for (Integer y : B) {
				tempvar=new Complex(0,(Math.PI/N)*2*y*(Math.floor((interval.get(0)+interval.get(1))/2)));
				tempvar=tempvar.exp();
				tempvar=tempvar.times(qfq.get((x-y+N) % N));
				sumvar=sumvar.plus(tempvar);
			}
			sumvar=sumvar.div(new Complex(B.size(),0));
			sqnorm=sumvar.mod()*sumvar.mod();
			est+=sqnorm;
			sumvar=new Complex(0,0);
		}
		est/=A.size();
		if(est>=((5*threshold)/36)) return 1;
		return 0;
	}

	private static Complex f(int i,int N) {
		if (xml==1) return poly.eval(i, N);
		System.out.println("Please enter the real part of f(" + i + "):");
		double re=sc.nextDouble();
		System.out.println("Please enter the imaginary part of f(" + i + "):");
		double im=sc.nextDouble();
		return (new Complex(re,im));
	}

	public static List<Set<Integer>> generate_Queries(int N,double gamma,double fnorm,double prob){
		double mAconst=0.00002,mBconst=0.00002;
		double eta=Math.min(Math.min(Math.sqrt(gamma),gamma/fnorm),gamma);
		int i;
		int mA=(int) (mAconst*(fnorm/eta)*(fnorm/eta)*Math.log(1.0/prob));
		int mB=(int) (mBconst*(fnorm/eta)*(fnorm/eta)*Math.log(fnorm/(prob*gamma)));		
//		int mA=(int) (mAconst*(1.0/(gamma*gamma))*Math.log(1.0/prob));
//		int mB=(int) (mBconst*(1.0/(gamma*gamma))*Math.log(1.0/(prob*gamma)));
		System.out.println("mA is: " + mA + " mB is: " + mB);
		Set<Integer> A=new HashSet<Integer>();
		List<Set<Integer>> listof_Sets = new ArrayList<Set<Integer>>();
		listof_Sets.add(A);
		Random rnd=new Random();
		while(A.size()<Math.min(mA,N)){
			A.add(rnd.nextInt(N));
		}
		for(i=1;i<log2(N);i++){
			listof_Sets.add(new HashSet<Integer>());
			while(listof_Sets.get(i).size()<Math.min(mB,Math.pow(2,i-1))){
				listof_Sets.get(i).add(rnd.nextInt((int) Math.pow(2,i-1)));
			}
		}
		listof_Sets.add(new HashSet<Integer>());
		while(listof_Sets.get(i).size()<Math.min(mB,Math.pow(2,i-1))){
			listof_Sets.get(i).add(rnd.nextInt(N));
		}

		return listof_Sets;
	}



	private static int log2(int n) {
		return ((int) (Math.log(n)/Math.log(2)));
	}


}
